package com.LeeCode;

/**
 * 最多可达成的换楼请求数目
 */

public class Code1601 {
    public static void main(String[] args) {
        int n = 5;
        int[][] request = {
                {0, 1}, {1, 0}, {0, 1}, {1, 2}, {2, 0}, {3, 4}
        };
        System.out.println(new Code1601().maximumRequests(n, request));
    }

    public int maximumRequests(int n, int[][] requests) {
        int ans = 0;

        next:
        for (int index = 1; index < (1 << requests.length); index++) {
            int[] cnt = new int[n];
            for (int i = 0; i < requests.length; i++) {
                if ((index >> i & 1) == 1) {
                    int from = requests[i][0], to = requests[i][1];
                    cnt[from]--;
                    cnt[to]++;
                }
            }
            for (int i = 0; i < n; i++) {
                if (cnt[i] != 0)
                    continue next;
            }
            ans = Math.max(ans, Integer.bitCount(index));
        }
        return ans;
    }
}
